package test.examation;

import java.util.Arrays;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;

public class 老虎集团 {
    public static void main(String[] args) {
        int tasks[][]={{0,1},{1,2},{1,3}};
        System.out.println(maxLevel(2,1,tasks));


        int trips[][]={{20,3,60},{30,1,99},{25,5,100},{32,20,60},{34,10,30}};
        int capacity=45;
        int i = m3(trips, capacity);
        System.out.println(i);

    }
    public static int maxLevel (int x, int level, int[][] tasks) {//每次选择任务的时候，都尽量去选择可以获得等级最多的任务就ok了
        // write code here
//        return m1(x, level, tasks);

//        return m2(x, level, tasks);

        return m4(x, level, tasks);
    }

    private static int m4(int x, int level, int[][] tasks) {
        int max=0;
        if (x==0){
            return level;
        }
        for (int i = 0; i < tasks.length; i++) {
            if (level>=tasks[i][0]){
                max=Math.max(max,tasks[i][1]);
            }
        }
        return maxLevel(x-1,level+max,tasks);
    }

    private static int m2(int x, int level, int[][] tasks) {
        if(x==0) return level;
        Arrays.sort(tasks, (o1, o2) -> o1[0] - o2[0]);
        PriorityQueue<Integer> pq=new PriorityQueue<>(tasks.length,(o1, o2) -> o2-o1);//存储任务的提升等级
        int i=0;
        for(int j=0;j<x;j++){
            while(i<tasks.length&&level>=tasks[i][0]){
                pq.add(tasks[i][1]);
                i++;
            }
            level+=pq.poll();
        }
        return level;
    }

    private static int m1(int x, int level, int[][] tasks) {//使用排序加set

        if (x == 0) return level;

        //任务需要的等级从小到大排序
        Arrays.sort(tasks, (o1, o2) -> o1[0] - o2[0]);
        if (level < tasks[0][0]) return level;

        //任务的经验从大到小排序
        Arrays.sort(tasks, (o1, o2) -> o2[1] - o1[1]);
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < x; i++) {
            for (int j = 0; j < tasks.length; j++) {
                if (!set.contains(j) && level >= tasks[j][0]) {
                    level += tasks[j][1];
                    set.add(j);
                    break;
                } else if (set.contains(j)) {
                    continue;

                }
            }
        }
        return level;
    }

    public static int mincarcount(int trips[][],int capacity){//计算需要的最少车辆
//        return m3(trips, capacity);

        //多个线段的最大重叠
        int[] roads = new int[1001];
        int m = trips.length;
        for (int i = 0;i < m;i++)
        {
            for (int j = trips[i][1];j <= trips[i][2];j++)
            {
                roads[j] += trips[i][0];
            }

        }
        int count = 0;
        for (int i = 0;i < 1001;i++)
            count = Math.max(count, roads[i]);
        int res = count % capacity == 0 ? count/capacity : count/capacity + 1;
        return res;

    }

    private static int m3(int[][] trips, int capacity) {
        // 先按各班次的的起始站点排序
        Arrays.sort(trips, (a, b) -> a[1] - b[1]);

        int n = trips.length;
        int max = trips[0][0]; // max是记录车上人数最多的人数。初始是第一班次的人数


        // 利用线段去理解，第i个班次及之前的最大人数值
        for (int i = 1; i < n; i++) {
            int cur = 0; // 当前班次及之前车上最多时候装的人数
            for (int j = 0; j < i; j++) {
                if ( trips[j][2]>trips[i][1]) {//如果之前的尾大于新的首的话说明有重叠
                    cur += trips[j][0];
                }
            }

            cur += trips[i][0];
            max = Math.max(cur, max);
        }

        return max / capacity + 1;
    }
}
